The present invention is related to computer-aided design, and more particularly to computer-aided design systems for detail routing of integrated circuits.
Integrated circuits comprise a collection of components, including but not limited to transistors, resistors, and capacitors, fabricated on a semiconductor substrate. The components are connected with metal interconnections, called wires, to form a system such as a microprocessor. Integrated circuit performance has been improving because the components and the wires are being fabricated in smaller sizes to increase the density of the integrated circuits. However, as the density of the integrated circuits increase, the complexity also increases. Most integrated circuits are so complex that it is no longer reasonable to use manual design techniques to design them; rather, computer-aided design (CAD) systems are used to aid in the design of such integrated circuits.
Some of the functions generally performed by a CAD system include, but are not limited to, placement, global routing and detail routing of integrated circuit elements. When placing elements of an integrated circuit in a layout, the CAD system attempts to make intelligent decisions about where connectors to the circuit element should be located and also about how the circuit elements should be oriented or positioned relative to one another. After placement of the circuit elements, the next act performed by the CAD system is typically global routing of the circuit elements. Global routing attempts to logically determine what general path each interconnection is going to take. Global routing decisions are made based on the available avenues formed by the placement of the circuit elements and are assigned in consideration of the various costs (i.e. such as to incur the shortest amount of interconnect between the connectors.) After the global router has assigned the general flow of interconnect lines, a detail router takes over and actually attempts to make the interconnect lines fit the assignments made by the global router. The detail router attempts to comply with the design rules for the circuit.
Generally, the detail routing process has three phases. In the first phase, the search space is modeled. The search space is the area available for the circuit layout. In the second phase, the actual search for a best route takes place using the model of the search space created in the first phase. In the third phase, a ripup and reroute strategy is applied to either clean up any design-rule violations and/or complete the unrouted nets.
The model of the search space used by a detail router includes obstacles and their relationships. Examples of obstacles include, but are not limited to, circuit elements, contacts that cannot be crossed, or wires that have already been routed. The obstacles need to be modeled in such a way that the subsequent search is convenient and that ensures design rule correctness of the resulting layout.
The layout models previously used by detail routers are very simplistic. Generally, the layout models divide topologically the search space into black and white regions. A white region is a permitted location for routing. A black region is a forbidden location for routing. Such a simplistic layout model has several disadvantages. For example, such a layout model does not effectively use all of the search space to route connections. Furthermore, it is difficult to model sophisticated design rules required by modem VLSI systems using such a simple model.
For these and other reasons, there is a need for the present invention.
Some embodiments of the invention include a computerized method of modeling a layout for a circuit design comprising receiving a plurality of circuit elements and receiving a plurality of design rules for a layout comprising the plurality of circuit elements. The computerized method further includes generating a layout model through computer automated operations wherein one or more constraints corresponding to the plurality of design rules effective at each point in a search space of the layout model are indicated by a color associated with the point.
Other embodiments are described and claimed.